package demo.DataStrucAndAlgo;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/21-07-21-18:59
 * @Description：demo.DataStrucAndAlgo   稀疏数组
 * 普通数组当存在大量无效值（如 0）时，将普通数组中的有效值（非0）通过 行，列，具体数据 的形式保存入n行3列的数组中，
 * 这个数组叫稀疏数组。稀疏数组压缩了原数组内容。
 */
public class Sparse_Array {
    public static void main(String[] args) {
        //模拟棋盘二维数组并赋值，黑子1，蓝子2
        int chessArr[][] = new int[11][11];
        chessArr[1][2] = 1;     //2行3列为黑子
        chessArr[2][5] = 2;     //3行6列为蓝子
        chessArr[4][3] = 1;     //5行4列为黑子

        //遍历数组取有效值个数
        int count = 0;   //有效值计数器
        for (int arr[]: chessArr){
            for (int temp : arr) {
                if(temp != 0){
                    count++;
                }
            }
        }

        //二维数组 -> 稀疏数组
        //1、基础信息录入
        int sparseArr[][] = new int[count+1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = count;
        //2、有效值信息录入
        count = 1;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if(chessArr[i][j] != 0){
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                    count++;
                }
            }
        }
        for (int[] arr : sparseArr) {      //打印稀疏数组
            for (int temp : arr) {
                System.out.print(temp + " ");
            }
            System.out.println();
        }

        //稀疏数组  ->  二维数组
        //1、创建二维数组
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        //有效值导入
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        for (int[] arr : chessArr2) {
            for (int temp : arr) {
                System.out.print(temp + " ");
            }
            System.out.println();
        }
    }
}
